import java.util.Arrays;

//背包问题(贪心算法)
public class GreedyPackage {

    private int MAX_WEIGHT = 150;//定义背包的容量
    private int[] weights = new int[]{35,30,60,50,40,10,25};//物品的重量
    private int[] values = new int[]{10,40,30,50,35,40,30};//物品的价值

    /*private void packageGreedy(int capacity,int[] weights,int[] values){
        int n = weights.length;
        double[] r = new double[n]; //性价比数组
        int[] index = new int[n];   //按性价比排序物品的下标
        for(int i = 0;i < n;i++){
            r[i] = (double) values[i] / weights[i];//计算每个物品的性价比
            index[i] = i;//默认排序
        }

        double temp = 0;    //对性价比进行排序
        for(int i = 0;i < n - 1;i++){
            for(int j = i + 1;j < n;j++){
                if(r[i] < r[j]){
                    temp = r[i];
                    r[i] = r[j];
                    r[j] = temp;
                    int x = index[i];
                    index[i] = index[j];
                    index[j] = x;
                }
            }
        }

        //将排序好的重量和价值分别存到数组中
        int[] w1 = new int[n];
        int[] value1 = new int[n];

        for(int i = 0;i < n;i++){
            w1[i] = weights[index[i]];
            value1[i] = values[index[i]];

        }
        System.out.println("按照性价比排序后存放重量和价值的数组为：");
        for(int v:w1){
            System.out.print(v+"\t");
        }
        System.out.println();
        System.out.println("********************************");
        for(int i:value1){
            System.out.print(i+"\t");
        }
        System.out.println();
        int[] x = new int[n];
        int maxValue = 0;
        for(int i = 0;i < n;i++){
            if(w1[i] <= capacity){   //表明还可以装得下
                x[i] = 1;   //表示该物品被装了
                capacity = capacity - w1[i];//背包装入一个物品后剩余的容量
                maxValue += value1[i];//背包装入物品后的价值
        }
        }
        System.out.println("总共放下的物品数量:" + Arrays.toString(x));
        System.out.println("最大价值为:" + maxValue);
    }*/
    private void packageGreedy(int capcity,int[] weights,int[] values){
        int n=weights.length;
        double[] r=new double[n];//创建一个数组用来存放物品的性价比
        int[] index=new int[n];//创建一个数组用来记录按性价比排序后的物品的下标
        for(int i=0;i<n;i++){
            r[i]=(double)values[i]/weights[i];//计算每个物品的性价比
            index[i]=i;
        }

        //排序
        double temp=0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(r[i]<r[j]){
                   temp=r[i];
                   r[i]=r[j];
                   r[j]=temp;
                   int x=index[i];
                   index[i]=index[j];
                   index[j]=x;

                }
            }
        }
        //将排序好的物品放入到新的数组中
        int[] w=new int[n];
        int[] value=new int[n];

        for (int i = 0; i <n ; i++) {
            w[i]=weights[index[i]];
            value[i]=values[index[i]];
        }

        //打印输出按性价比排序的物品的重量和价值数组
        System.out.println("按照性价比排序后的物品的重量为：");
        for(int v:w){
            System.out.print(v+"\t");
        }
        System.out.println();
        System.out.println("按照性价比排序后的物品的价值为：");
        for(int i:value){
            System.out.print(i+"\t");
        }
        System.out.println();

        //将物品依次放入背包中
        int maxValue=0;
        int[] flag=new int[n];//创建一个数组用来标志物品是否被放入  放入置为1 不放入置为0
        for (int i = 0; i <n ; i++) {
            if(w[i]<=capcity){
                flag[i]=1;
                capcity-=w[i];
                maxValue+=value[i];

            }
        }

        //最后打印输出物品放入情况和最大价值
        System.out.println("被放入背包的物品为："+Arrays.toString(flag));
        System.out.println("背包的最大价值为："+maxValue);
    }


    public static void main(String[] args){
        GreedyPackage g = new GreedyPackage();
        g.packageGreedy(g.MAX_WEIGHT,g.weights,g.values);
    }
}